Sherman–Morrison formula

In mathematics, in particular linear algebra, the Sherman–Morrison formula,^[1]^[2]^[3] named after Jack Sherman and Winifred J. Morrison, computes the inverse of the sum of an invertible matrix $A$ and the dyadic product, $u v^T$ , of a column vector $u$ and a row vector $v^T$ . The Sherman–Morrison formula is a special case of the Woodbury formula. Though named after Sherman and Morrison, it appeared already in earlier publications ^[4]

1 Statement
2 Application
3 Verification
4 See also
5 References
6 External links

Statement

Suppose $A$ is an invertible square matrix and $u$ , $v$ are vectors. Suppose furthermore that $1 %2B v^T A^{-1}u \neq 0$ . Then the Sherman–Morrison formula states that

$(A%2Buv^T)^{-1} = A^{-1} - {A^{-1}uv^T A^{-1} \over 1 %2B v^T A^{-1}u}.$

Here, $uv^T$ is the dyadic product of two vectors $u$ and $v$ . The general form shown here is the one published by Bartlett.^[5]

Application

If the inverse of $A$ is already known, the formula provides a numerically cheap way to compute the inverse of $A$ corrected by the matrix $uv^T$ (depending on the point of view, the correction may be seen as a perturbation or as a rank-1 update). The computation is relatively cheap because the inverse of $A%2Buv^T$ does not have to be computed from scratch (which in general is expensive), but can be computed by correcting (or perturbing) $A^{-1}$ .

Using unit columns (columns from the identity matrix) for $u$ or $v$ , individual columns or rows of $A$ may be manipulated and a correspondingly updated inverse computed relatively cheaply in this way.^[6] In the general case, where $A^{-1}$ is a $n$ times $n$ matrix and $u$ and $v$ are arbitrary vectors of dimension $n$ , the whole matrix is updated^[5] and the computation takes $3n^2$ scalar multiplications.^[7] If $u$ is a unit column, the computation takes only $2n^2$ scalar multiplications. The same goes if $v$ is a unit column. If both $u$ and $v$ are both unit columns, the computation takes only $n^2$ scalar multiplications.

Verification

We verify the properties of the inverse. A matrix $Y$ (in this case the right-hand side of the Sherman–Morrison formula) is the inverse of a matrix $X$ (in this case $A%2Buv^T$ ) if and only if $XY = YX = \text{I}$ .

We first verify that the right hand side ( $Y$ ) satisfies $XY = \text{I}$ .

$XY = (A %2B uv^T)\left( A^{-1} - {A^{-1} uv^T A^{-1} \over 1 %2B v^T A^{-1}u}\right)$

$= AA^{-1} %2B uv^T A^{-1} - {AA^{-1}uv^T A^{-1} %2B uv^T A^{-1}uv^T A^{-1} \over 1 %2B v^TA^{-1}u}$

$= I %2B uv^T A^{-1} - {uv^T A^{-1} %2B uv^T A^{-1}uv^T A^{-1} \over 1 %2B v^T A^{-1}u}$

$= I %2B uv^T A^{-1} - {u(1 %2B v^T A^{-1}u) v^T A^{-1} \over 1 %2B v^T A^{-1}u}$

Note that $v^T A^{-1}u$ is a scalar, so $(1%2Bv^T A^{-1}u)$ can be factored out, leading to:

$XY= I %2B uv^T A^{-1} - uv^T A^{-1} = I.\,$

In the same way, it is verified that

$YX = \left(A^{-1} - {A^{-1}uv^T A^{-1} \over 1 %2B v^T A^{-1}u}\right)(A %2B uv^T) = I.$

Following is an alternate verification of the Sherman–Morrison formula using the easily verifiable identity

${{\left( I%2Bw{{v}^{T}} \right)}^{-1}}=I-\frac{w{{v}^{T}}}{1%2B{{v}^{T}}w}$

Let $u=Aw$ and $A%2Bu{{v}^{T}}=A\left( I%2Bw{{v}^{T}} \right)$ , then

${{\left( A%2Bu{{v}^{T}} \right)}^{-1}}={{\left( I%2Bw{{v}^{T}} \right)}^{-1}}{{A}^{-1}}=\left( I-\frac{w{{v}^{T}}}{1%2B{{v}^{T}}w} \right){{A}^{-1}}$

Substituting $w={{A}^{-1}}u$ gives

${{\left( A%2Bu{{v}^{T}} \right)}^{-1}}=\left( I-\frac{{{A}^{-1}}u{{v}^{T}}}{1%2B{{v}^{T}}{{A}^{-1}}u} \right){{A}^{-1}}={{A}^{-1}}-\frac{{{A}^{-1}}u{{v}^{T}}{{A}^{-1}}}{1%2B{{v}^{T}}{{A}^{-1}}u}$

References

^ Sherman, Jack; Morrison, Winifred J. (1949). "Adjustment of an Inverse Matrix Corresponding to Changes in the Elements of a Given Column or a Given Row of the Original Matrix (abstract)". Annals of Mathematical Statistics 20: 621. doi:10.1214/aoms/1177729959.
^ Sherman, Jack; Morrison, Winifred J. (1950). "Adjustment of an Inverse Matrix Corresponding to a Change in One Element of a Given Matrix". Annals of Mathematical Statistics 21 (1): 124–127. doi:10.1214/aoms/1177729893. MR 35118. Zbl 0037.00901.
^ Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 2.7.1 Sherman-Morrison Formula", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8, http://apps.nrbook.com/empanel/index.html?pg=76
^ Hager, William W. (1989). "Updating the inverse of a matrix". SIAM Review 31 (2): 221–239. doi:10.1137/1031049. JSTOR 2030425. MR 997457.
^ ^a ^b Bartlett, M. S. (1951). "An Inverse Matrix Adjustment Arising in Discriminant Analysis". Annals of Mathematical Statistics 22 (1): 107–111. doi:10.1214/aoms/1177729698. MR 40068. Zbl 0042.38203.
^ Langville, Amy N. and Meyer, Carl D., "Google's PageRank and Beyond: The Science of Search Engine Rankings", Princeton University Press, 2006, p. 156
^ Update of the inverse matrix by the Sherman-Morrison formula

External links

Weisstein, Eric W., "Sherman-Morrison formula" from MathWorld.